/**
 * https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
 * 寻找两个正序数组的中位数
 * @param nums1 
 * @param nums2 
 */
const findMedianSortedArrays = (nums1: number[], nums2: number[]): number => {
    // 获取长度
    const l1 = nums1.length,
        l2 = nums2.length;

    // 只有一个元素的情况
    if (l1 + l2 === 1) {
        return nums1[0] ?? nums2[0]
    }

    // 使用归并排序将两个数组排序
    let len = l1 + l2;

    let mid = len >> 1,
        li = 0,
        ri = 0;

    let arr = [0, 0]

    while ((li + ri) <= mid) {
        if ( nums2[ri] == undefined || 
            nums1[li] !== undefined && nums1[li] <= nums2[ri]) {
            arr = [arr[1], nums1[li]]
            li++
        } else {
            arr = [arr[1], nums2[ri]];
            ri++;
        }
    }

    return (len & 1) === 1 ? arr[1] : (arr[0] + arr[1]) / 2
};




const findMedianSortedArrays2 = (nums1: number[], nums2: number[]): number => {
    // 获取长度
    const l1 = nums1.length,
        l2 = nums2.length;

    if (l1 + l2 === 1) {
        return nums1[0] ?? nums2[0]
    }

    // 使用归并排序将两个数组排序
    // 1. 创建长度为l1 + l2的数组
    const arr = new Array(l1 + l2);

    // 2. 确定ai, li, le, ri, re
    let ai = 0,
        li = 0,
        le = l1,
        ri = 0,
        re = l2,
        len = l1 + l2;

    while (li < le && ri < re) {
        if (nums2[ri] < nums1[li]) {
            // 右 < 左
            arr[ai] = nums2[ri++];
        } else {
            // 右 >= 左
            arr[ai] = nums1[li++]
        }
        ai++;
    }

    // 3. 左边先结束
    if (li >= le) {
        // 将右边的拷贝到数组中
        for (let i = ri; i < re; i++) {
            arr[ai++] = nums2[i]
        }
    }

    // 4. 右边先结束
    if (ri >= re) {
        // 将左边的拷贝到数组中
        for (let i = li; i < le; i++) {
            arr[ai++] = nums1[i];
        }
    }


    // 寻找中间的两个元素
    if ((len & 1) === 1) {
        // 数量是奇数的, 说明中位数就是中间的元素
        return arr[len >> 1]
    } else {
        // 数量是偶数的
        return (arr[len >> 1] + arr[(len >> 1) - 1]) / 2
    }
};

const a1: number[] = [1, 4],
    a2: number[] = []
// const a1: number[] = [1, 3, 5, 100],
//     a2: number[] = [2, 4, 6, 10]
const r2 = findMedianSortedArrays(a1, a2);
console.log(r2);